package com.demo.algorithms.sort;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * 希尔排序：时间复杂度为O(N*logN)
 * 将无序数组分割为若干个子序列，子序列不是逐段分割的，
 * 而是相隔特定的增量的子序列，对各个子序列进行插入排序；
 * 然后再选择一个更小的增量，再将数组分割为多个子序列进行排序。
 * 最后选择增量为1，即使用直接插入排序，使最终数组成为有序。
 * <p>
 * 希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。
 * 该方法又称缩小增量排序
 *
 * @author: 蔡奇峰
 * @date: 2020/7/19 16:08
 **/
public class ShellSort {

    public static void main(String[] args) {
//        int[] arr = {6, 2, 5, 2, 8, 66, 22, 17, 18, 1, 88, 98, 168, 178};
        int[] arr = new int[67180];
        for (int i = 0; i < 67180; i++) {

            arr[i] = new Random().nextInt(18060);
        }
        System.out.println("数组排序前：" + Arrays.toString(arr));

        long timeMillis = System.currentTimeMillis();
//        Arrays.sort(arr);
        sort(arr);
//        sortSwap(arr);
        long timeMilli = System.currentTimeMillis();

        System.out.println("数组排序后：" + Arrays.toString(arr));
        System.out.println("插入排序耗时：" + (timeMilli - timeMillis));
    }

    /**
     * 希尔排序（移动版）：插入排序的升级版
     * 分组进行插入排序。步长为： 数组大小 一直除2 直到为1 即（tap  /= 2 == 1)
     *
     * 两组对应的位置进行比较，即前面组第i个和后面组第i个进行比较（i 和 i + 步长 进行比较）
     *
     * @param arr 需要排序的数组
     */
    public static void sort(int[] arr) {
        // 增量(步长)，逐步缩小增量
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            // 从第个gap(增量）元素开始，进行排序
            for (int i = gap; i < arr.length; i++) {
                // 后面组的索引，辅助遍历后面组
                int index = i;
                // 插入的值
                int val = arr[index];
                // 前面组和后面组进行比较，小的在起那么，大的则移动到后面组
                while (index - gap >= 0 && arr[index - gap] > val) {
                    // 移动
                    arr[index] = arr[index - gap];
                    index -= gap;
                }
                // 在当前所在的组插入值，即后面组
                arr[index] = val;
            }

        }
    }

    /**
     * 希尔排序（交换版）:性能比简单插入排序低，不推荐使用
     *
     * @param arr 需要排序的数组
     */
    public static void sortSwap(int[] arr) {
        // 临时变量，存储大的
        int temp;
        // 增量(步长)，逐步缩小增量，第一个for循环是用于遍历每个组
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            // 从第个gap(增量）元素开始，进行排序，第二个for是遍历两个组进行比较
            for (int i = gap; i < arr.length; i++) {
                // 遍历前面组
                for (int j = i - gap; j >= 0; j -= gap) {
                    // 如果前面组大于后面组，则进行交换
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        // 交换
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }

            }
        }

    }

}
